package leetcode.code0043;

public class Solution71 {

	public String simplifyPath(String path) {
		int len = path.length(); // 原始字符串长度
		char[] chars = path.toCharArray();
		char[] ans = new char[len + 1]; // 结果字符集合，代替栈操作
		int[] starts = new int[len + 1];// 在ans中每个单词开头的索引
		int pans = 0;// 指向ans可用位置，最新的一个字符放在pans上，放上字符后要++后移
		int pstarts = 0;// 指向starts上记录着最后一个单词的位置
		ans[pans++] = '/';// 已知答案得开头是/
		starts[pstarts] = 1;// 第一个单词的开头位置是在ans上的索引是1（0是/）
		int dot = 0;// .的数量
		for (int i = 1; i < len; i++) {
			char c = chars[i];
			if (c == '.') {
				dot++;// 遇到.就计数
				ans[pans++] = '.';// 先放到结果集合上
			} else {
				if (dot == 1 && c == '/' && ans[pans - 2] == '/') {// 如果是一个.
					pans--;// ans上占用一个无效的. pans回退一个
				} else if (dot == 2 && c == '/' && ans[pans - 3] == '/') {// 如果是两个. 可以当做退目录
					pstarts = pstarts - 1;// pstarts指向的是..的开头，pstarts-1指向上一个单词的开头
					pans = pstarts >= 0 ? starts[pstarts] : 1;// 两个.将上一个单词回退掉，从这个位置开始记录新的单词
					pstarts = pstarts > 0 ? pstarts-- : 0;// pstarts指向最后一个可用的单词位置
				}
				dot = 0;// 重新记录点
				if (c == '/') {
					if (ans[pans - 1] != '/') {// 之前结果最后不是/，说明是文件目录分隔符
						ans[pans++] = '/';// 追加一个分隔符
						starts[++pstarts] = pans;// i+1的位置是下一个单词的开头
					}
				} else {
					ans[pans++] = c;// 不是.也不是/，追加到文件目录
				}
			}
		}
		if (dot == 1 && ans[pans - 2] == '/') {// 如果是一个.
			pans--;// ans上占用一个无效的. pans回退一个
		} else if (dot == 2 && ans[pans - 3] == '/') {// 如果是两个.
			pstarts = pstarts - 1;// pstarts指向的是..的开头，pstarts-1指向上一个单词的开头
			pans = pstarts >= 0 ? starts[pstarts] : 1;// 两个.将上一个单词回退掉，从这个位置开始记录新的单词
			pstarts = pstarts > 0 ? pstarts-- : 0;// pstarts指向最后一个可用的单词位置
		}
		pans = ans[pans - 1] == '/' && pans > 1 ? pans - 1 : pans;// -1去掉最后一个/ , 至少留一个/
		return new String(ans, 0, pans);
	}

	public static void main(String[] args) {
		Solution71 so = new Solution71();
		String ans = null;
		ans = so.simplifyPath("/a/./b/../../c/");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/hello./world/");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/hello/hello../hello../");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/.hidden");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/..hidden");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/...");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/a//b////c/d//././/..");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/a//b////c/d//././/.");// "/a/b/c"
		System.out.println(ans);
		ans = so.simplifyPath("/home/nice/..//.../...hello//./hello/");
		System.out.println(ans);
		ans = so.simplifyPath("/../");
		System.out.println(ans);
	}

}
